'''
其实就是BSF算法
'''


from typing import List
class TreeNode:
    def __init__(self, x):
        self.val = x  # 值
        self.left = None  # 左节点
        self.right = None  # 右节点

'''这种方法简洁但不标准，还慢'''
class Solution01:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        if not root:
            return []

        def bfs(queue):
            if not queue:
                return []
            res = [[node.val for node in queue]]
            '''
            sum()的作用是把list里面的二级list变成一级list
            即[[1, 2, 3, 4], [5, 6]] --> [1,2,3,4,5,6]
            注意只能降一级, 并且必须是上面的同级形式，
            [[1, 2, [3,4]], [5, 6]]这种多级混合的形式就不能用了
            '''
            next_queue = sum([[child for child in (node.left, node.right) if child] for node in queue if node], [])
            # print(type(next_queue))
            res += bfs(next_queue)
            return res

        return bfs([root])

'''第二种方法更标准'''
class Solution02:
    def levelOrder(self, root: TreeNode) -> List[List[int]]: #BFS
        if not root:return []
        queue = [root]
        res = []
        deepth = 0
        while queue:
            temp = []
            for _ in range(len(queue)): # 这里本身就是从上到下一行一行遍历的
                node = queue.pop(0)
                temp.append(node.val)
                if node.left:
                    queue.append(node.left)
                if node.right:
                    queue.append(node.right)
            # temp[::(-1) ** deepth] 把偶数行反相
            res.append(temp[::(-1)**deepth])
            # res.append(temp)
            deepth += 1
        return res


if __name__ == "__main__":
    tree = TreeNode(4)  # 添加根节点
    tree.left = TreeNode(9)  # 添加根左子树
    tree.right = TreeNode(0)  # 添加根右子树，以下以此类推
    tree.left.left = TreeNode(5)
    tree.left.right = TreeNode(1)
    tree.right.left = TreeNode(3)
    tree.right.right = TreeNode(2)
    tree.left.left.left = TreeNode(10)
    tree.right.left.right = TreeNode(7)

    s1 = Solution01()
    print(s1.levelOrder(tree))
    s2 = Solution02()
    print('s2: ', s2.levelOrder(tree))
    # [4, 9, 5, 10, 1, 0, 3, 7, 2]

    '''sum()列表中的使用 测试'''
    a = [[1, 2, [3,4]], [5, 6]]
    b = []
    print('测试sum()：', sum(a, b))














